
package Type_2_linked.title2_P707;


import Type_2_linked.common.ListNode;

//707.设计链表(单链表)  所有节点下标从 0 开始。
public class P707_1 {

    private ListNode head;   //TODO 虚拟头结点
    private int size;      //链表长度

    public P707_1() {
        this.size = 0;
        this.head = new ListNode(-1);
    }

    /**
     * 获取链表中第 index 个节点的值。如果索引无效，则返回-1。
     */
    public int get(int index) {
        if (index < 0 || index >= size) {  //TODO 等于也不行 因为索引从0开始
            return -1;
        }

        ListNode currentNode = head;

        for (int i = 0; i <= index; i++) {  //获取第index处的节点
            currentNode = currentNode.next;  //移动指针
        }

        return currentNode.val;
    }

    /**
     * 在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
     * TODO 先新后旧
     */
    public void addAtHead(int val) {
        ListNode newHead = new ListNode(val);


        //TODO 插入链表时，必须先设置新节点的指针，再修改源节点的指针。(防止成环)
        newHead.next = head.next;  //新节点 指向 原第一个节点
        head.next = newHead;       //头结点 连接新节点

        size++;//长度加一
//        ListNode.printListNode(this.head.next);
    }

    /**
     * 将值为 val 的节点追加到链表的最后一个元素。
     */
    public void addAtTail(int val) {
        ListNode newTail = new ListNode(val);

        ListNode currentNode = head;
        while (currentNode.next != null) {  //遍历找到最后一个元素
            currentNode = currentNode.next;
        }
        currentNode.next = newTail;

        size++;//长度加一

//        ListNode.printListNode(this.head.next);

    }

    /**
     * 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。
     * 如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。
     * 如果 index 比长度更大，该节点将 不会插入 到链表中。
     */
    public void addAtIndex(int index, int val) {

        if (index < 0 || index > size) return;

        if (index == size) {
            addAtTail(val);
        } else {
            ListNode newNode = new ListNode(val);

            ListNode currentNode = head;
            for (int i = 0; i < index; i++) {   //TODO 不能等于
                currentNode = currentNode.next;  //移动
            }

            newNode.next = currentNode.next;  //新节点 连接 老节点的下一个节点
            currentNode.next = newNode;   //老节点 连接 新节点

            size++;

            ListNode.printListNode(this.head.next);
        }
    }

    /**
     * 如果索引 index 有效，则删除链表中的第 index 个节点
     */
    public void deleteAtIndex(int index) {

        if (index < 0 || index >= size) return;  //TODO 等于也不行 因为索引从0开始

        ListNode currentNode = head;
        for (int i = 0; i < index; i++) {   //TODO 不能等于
            currentNode = currentNode.next;  //移动
        }

        currentNode.next = currentNode.next.next;
        size--;

        ListNode.printListNode(this.head.next);
    }


    public static void main(String[] args) {

        P707_1 myLinkedList = new P707_1();

        myLinkedList.addAtHead(1);
        myLinkedList.addAtTail(3);
        myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
        System.out.println(myLinkedList.get(1));              // 返回 2
        myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
        System.out.println(myLinkedList.get(1));              // 返回 3
    }
}